package leetcode.year2021.month11;

// 41. 缺失的第一个正数
public class _08_2FirstMissingPositive41 {
  // 把所有数遍历赋值到对应的位置，要注意的是要满足条件， 第三个条件是为了避免死循环
  // 每次交换过后，都要继续判断交换回来的值，如果不满足，这个值才能被放弃
  public int firstMissingPositive(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
      while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i]-1] != nums[i]){
        swap(nums,nums[i]-1,i);
      }
    }
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] != i+1) {
        return i+1;
      }
    }
    return nums.length+1;
  }

  private void swap(int[] nums, int i, int i1) {
    int temp = nums[i];
    nums[i] = nums[i1];
    nums[i1] = temp;
  }


  /**
   * 41. 缺失的第一个正数
   * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
   *
   * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
   *
   *
   * 示例 1：
   *
   * 输入：nums = [1,2,0]
   * 输出：3
   * 示例 2：
   *
   * 输入：nums = [3,4,-1,1]
   * 输出：2
   * 示例 3：
   *
   * 输入：nums = [7,8,9,11,12]
   * 输出：1
   *
   *
   * 提示：
   *
   * 1 <= nums.length <= 5 * 105
   * -231 <= nums[i] <= 231 - 1
   */
}
